home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1 Issue 2 / PDCD-1 - Issue 02.iso / _utilities / utilities / 003 / _gs / !GS / c / IALLOC < prev    next >
Text File  |  1991-10-26  |  11KB  |  358 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* ialloc.c */
  21. /* Memory allocator for Ghostscript interpreter */
  22. #include <stdio.h>        /* for NULL */
  23. #include "gs.h"
  24. #include "memory_.h"
  25. #include "alloc.h"
  26. #include "astate.h"
  27.  
  28. #ifdef DEBUG
  29. extern char gs_debug[128];
  30. #endif
  31.  
  32. /* Forward references */
  33. private int alloc_add_chunk(P2(alloc_state_ptr, uint));
  34. private char *alloc_large(P3(alloc_state_ptr, uint, char *));
  35. private void alloc_free_large(P3(char *, uint, char *));
  36.  
  37. /* The only allocator instance (for now). */
  38. private alloc_state as_current;
  39. alloc_state_ptr alloc_state_current = &as_current;
  40.  
  41. /* Debugging printout */
  42. #ifdef DEBUG
  43. #  define alloc_print(rtag, tag, blk, sz)\
  44.     if ( gs_debug['A'] )\
  45.       fprintf(gs_debug_out, "[a:%c:%c:%s] %lx(%u)\n", rtag, tag,\
  46.           client_name, (ulong)blk, sz)
  47. #  define alloc_print_large(rtag, tag, blk, sz)\
  48.     if ( gs_debug['A'] | gs_debug['a'] )\
  49.       fprintf(gs_debug_out, "[a:%c:%c:%s] %lx(%u)\n", rtag, tag,\
  50.           client_name, (ulong)blk, sz)
  51. #else
  52. #  define alloc_print(rtag, tag, blk, sz)
  53. #  define alloc_print_large(rtag, tag, blk, sz)
  54. #endif
  55.  
  56. /* ------ Initialize/status ------ */
  57.  
  58. /* Initialize the allocator */
  59. void
  60. alloc_init(proc_alloc_t palloc, proc_free_t pfree, uint chunk_size)
  61. {    register alloc_state_ptr ap = &as_current;
  62.     memset(ap, 0, sizeof(alloc_state));    /* do it all at once */
  63.     ap->chunk_size = chunk_size;
  64.     ap->big_size = chunk_size / 4;
  65.     ap->palloc = palloc;
  66.     ap->pfree = pfree;
  67.        {    extern void alloc_save_init(P0());
  68.         alloc_save_init();
  69.        }
  70. }
  71.  
  72. /* Return the status of the allocator: space used, total space. */
  73. void
  74. alloc_status(long *pused, long *ptotal)
  75. {    register alloc_state_ptr ap = &as_current;
  76.     *pused = (ap->cbot - ap->cbase) + (ap->climit - ap->ctop) + ap->used;
  77.     *ptotal = ap->total;
  78. }
  79.  
  80. /* ------ Allocation and freeing ------ */
  81.  
  82. /* Allocate an object.  Return 0 if not enough room. */
  83. char *
  84. alloc(uint num_elts, uint elt_size, char *client_name)
  85. {    register alloc_state_ptr ap = &as_current;
  86.     uint size = num_elts * elt_size;
  87.     uint block_size;
  88.     uint left;
  89.     if ( size >= ap->big_size )
  90.        {    /* Large object, do a separate malloc. */
  91.         char *block = alloc_large(ap, size, client_name);
  92.         if ( block != NULL ) return block;
  93.        }
  94.     block_size = align_round(size);
  95.     if ( block_size <= max_chain_size )
  96.        {    /* See if we can use a freed block. */
  97.         char **fptr = &ap->free[block_size >> log2_align_mod];
  98.         char *block = *fptr;
  99.         if ( block != 0 )
  100.            {    *fptr = *(char **)block;
  101.             alloc_print('+', '#', block, size);
  102.             return block;
  103.            }
  104.        }
  105.     left = ap->ctop - ap->cbot;
  106.     if ( block_size > left )
  107.        {    uint csize = ap->chunk_size;
  108.         while ( !alloc_add_chunk(ap, csize) )
  109.            {    alloc_print('+', '?', (ulong)0, size);
  110.             /* Things are desperate, but perhaps not hopeless. */
  111.             if ( (csize >>= 1) < block_size ) return 0;
  112.            }
  113.        }
  114.     if ( elt_size == 1 )
  115.        {    /* Unaligned block */
  116.         ap->ctop -= size;
  117.         alloc_print('+', '>', ap->ctop, size);
  118.         return (char *)ap->ctop;
  119.        }
  120.     else
  121.        {    /* Aligned block */
  122.         char *block = (char *)ap->cbot;
  123.         ap->cbot += block_size;
  124.         alloc_print('+', '<', block, size);
  125.         return block;
  126.        }
  127. }
  128.  
  129. /* Free an object, if possible. */
  130. /* Note that if a save is in effect, objects in chunks older than */
  131. /* the save, and objects allocated with malloc before the save, */
  132. /* must not be freed. */
  133. void
  134. alloc_free(char *cobj, uint num_elts, uint elt_size, char *client_name)
  135. {    register alloc_state_ptr ap = &as_current;
  136.     uint size = num_elts * elt_size;
  137.     uint block_size;
  138.     if ( size >= ap->big_size )
  139.        {    /* Object was allocated with malloc. */
  140.         alloc_free_large(cobj, size, client_name);
  141.         return;
  142.        }
  143. #define obj ((byte *)cobj)
  144.     else if ( obj == ap->ctop )
  145.        {    /* Don't free the object if we're in a save and */
  146.         /* this object wasn't allocated since the save. */
  147.         if ( ap->save_level == 0 ||
  148.              ap->current.save_level >= ap->save_level ||
  149.              /* We know the current chunk is the same as */
  150.              /* the one in as->saved->state */
  151.              obj < ap->saved_ctop
  152.            )
  153.             ap->ctop += size;
  154.         alloc_print('-', '>', obj, size);
  155.         return;
  156.        }
  157.     else if ( obj + (block_size = align_round(size)) == ap->cbot )
  158.        {    /* Freeing an aligned object.  Same check. */
  159.         if ( ap->save_level == 0 ||
  160.              ap->current.save_level >= ap->save_level ||
  161.              obj >= ap->saved_cbot
  162.            )
  163.             ap->cbot = obj;
  164.         alloc_print('-', '<', obj, size);
  165.         return;
  166.        }
  167.     else if ( !ptr_is_in_chunk(obj, &ap->current) )
  168.        {    /* In another segment, check its save level. */
  169.         int level = ap->save_level;
  170.         alloc_chunk *cp = ap->current.next;
  171.         for ( ; ; cp = cp->next )
  172.           { if ( cp != 0 )
  173.               { switch ( cp->save_level - level )
  174.               {
  175.               case 0:
  176.                 if ( ptr_is_in_chunk(obj, cp) )
  177.                   { if ( ptr_lt(obj, cp->bot) ) goto pbf;
  178.                   else break;
  179.                   }
  180.                 else continue;
  181.               case -1:
  182.                 /* Might be alloc'ed since the save, */
  183.                 /* or might not be aligned. */
  184.                 if ( ptr_lt(obj, ap->saved_cbot) )
  185.                   goto pbf;
  186.               }
  187.               }
  188.             /* Older save level, not freeable. */
  189.             alloc_print('-', '\\', obj, size);
  190.             return;
  191.           }
  192. pbf:        /* If we get here, OK to put the block on a free list. */
  193.         ;
  194.        }
  195.     else if ( obj >= ap->cbot )    /* not aligned object, punt */
  196.        {    alloc_print('-', '~', obj, size);
  197.         return;
  198.        }
  199.     /* Put on a free list if small enough */
  200.     alloc_print('-', '#', obj, size);
  201.     if ( block_size <= max_chain_size && block_size >= sizeof(char **) )
  202.        {    char **fptr = &ap->free[block_size >> log2_align_mod];
  203.         *(char **)cobj = *fptr;
  204.         *fptr = cobj;
  205.        }
  206. #undef obj
  207. }
  208.  
  209. /* Grow an object.  This may require allocating a new copy. */
  210. /* Return 0 if not enough room. */
  211. /****** Note: the object must have been allocated at
  212.  ****** the current save level. */
  213. byte *
  214. alloc_grow(byte *obj, uint old_num, uint new_num, uint elt_size,
  215.   char *client_name)
  216. {    register alloc_state_ptr ap = &as_current;
  217.     uint old_size = old_num * elt_size;
  218.     uint new_size = new_num * elt_size;
  219.     byte *nobj;
  220.     if ( new_size == old_size ) return obj;
  221.     if ( new_size < ap->big_size ) /* try to grow in place */
  222.       { uint old_block_size;
  223.         uint new_block_size;
  224.         if ( obj == ap->ctop )
  225.           { /* Might be able to grow in place */
  226.         uint diff = new_size - old_size;
  227.         if ( diff <= ap->ctop - ap->cbot )
  228.           { alloc_print('>', '>', obj, new_size);
  229.             ap->ctop -= diff;
  230.             memcpy(ap->ctop, obj, old_size);
  231.             return ap->ctop;
  232.           }
  233.           }
  234.         old_block_size = align_round(old_size);
  235.         new_block_size = align_round(new_size);
  236.         if ( obj + old_block_size == ap->cbot )
  237.           { /* Might be able to grow in place */
  238.         uint diff = new_block_size - old_block_size;
  239.         if ( diff <= ap->ctop - ap->cbot )
  240.           { alloc_print('>', '<', obj, new_size);
  241.             ap->cbot += diff;
  242.             return obj;
  243.           }
  244.           }
  245.       }
  246.     /* Can't grow in place.  Allocate a new object and copy. */
  247.     nobj = (byte *)alloc(new_num, elt_size, client_name);
  248.     if ( nobj == 0 ) return 0;
  249.     memcpy(nobj, obj, old_size);
  250.     alloc_free((char *)obj, old_num, elt_size, client_name);
  251.     alloc_print('>', '&', obj, new_size);
  252.     return nobj;
  253. }
  254.  
  255. /* Shrink an object. */
  256. /****** Note: the object must have been allocated at
  257.  ****** the current save level. */
  258. byte *
  259. alloc_shrink(byte *obj, uint old_num, uint new_num, uint elt_size,
  260.   char *client_name)
  261. {    register alloc_state_ptr ap = &as_current;
  262.     uint old_size = old_num * elt_size;
  263.     uint new_size = new_num * elt_size;
  264.     if ( new_size == old_size ) return obj;
  265.     if ( old_size >= ap->big_size )
  266.       { /* Allocate a new block. */
  267.         byte *nobj = (byte *)alloc(new_num, elt_size, client_name);
  268.         if ( nobj == 0 ) return obj; /* can't shrink, leave as is */
  269.         memcpy(nobj, obj, new_size);
  270.         alloc_free((char *)obj, old_num, elt_size, client_name);
  271.         alloc_print('<', '&', obj, new_size);
  272.         return nobj;
  273.       }
  274.     else if ( obj == ap->ctop )
  275.       { /* Move the object up in place. */
  276.         /* memcpy doesn't do this properly. */
  277.         register byte *from = obj + new_size;
  278.         register byte *to = obj + old_size;
  279.         while ( from > obj ) *--to = *--from;
  280.         obj = ap->ctop = to;
  281.       }
  282.     else
  283.       { uint new_block_size = align_round(new_size);
  284.         alloc_free((char *)(obj + new_block_size),
  285.                1, align_round(old_size) - new_block_size,
  286.                "alloc_shrink");
  287.       }
  288.     alloc_print('<', ' ', obj, new_size);
  289.     return obj;
  290. }
  291.  
  292. /* ------ Private routines ------ */
  293.  
  294. /* Allocate (with malloc) an object too large to be put in a chunk. */
  295. /* Return NULL on failure. */
  296. private char *
  297. alloc_large(alloc_state_ptr ap, uint size, char *client_name)
  298. {    alloc_block *mblock = (alloc_block *)
  299.         (*ap->palloc)(1, alloc_block_size + size, client_name);
  300.     char *block;
  301.     if ( mblock == NULL ) return NULL;
  302.     block = (char *)mblock + alloc_block_size;
  303.        alloc_print_large('+', '*', block, size);
  304.     mblock->next = ap->malloc_chain;
  305.     mblock->size = size;
  306.     mblock->save_level = ap->save_level;
  307.     mblock->cap = ap;
  308.     ap->malloc_chain = mblock;
  309.     ap->used += size;
  310.     ap->total += size;
  311.     return block;
  312. }
  313.  
  314. /* Allocate a new chunk.  Return true if successful. */
  315. private int
  316. alloc_add_chunk(register alloc_state_ptr ap, uint csize)
  317. {    char *space = (*ap->palloc)(1, csize, "alloc chunk");
  318.     long discard;
  319.     if ( space == NULL ) return 0;
  320.     ap->num_chunks++;
  321.     /* Accumulate statistics */
  322.     ap->total += csize;
  323.     alloc_status(&ap->used, &discard);
  324.     /* Stash the state of the old chunk */
  325.     if ( ap->current_ptr != 0 )    /* check for very first chunk */
  326.         *ap->current_ptr = ap->current;
  327.     /* Initialize the new chunk */
  328.     ap->cbase = ap->cbot = (byte *)space + align_round(sizeof(alloc_chunk));
  329.     ap->climit = ap->ctop = (byte *)(space + csize);
  330.     ap->current.next = ap->current_ptr;
  331.     ap->current.save_level = ap->save_level;
  332.     ap->current_ptr = (alloc_chunk *)space;
  333.     return 1;
  334. }
  335.  
  336. /* Free a large object (allocated with malloc). */
  337. private void
  338. alloc_free_large(char *cobj, uint size, char *client_name)
  339. {    alloc_block **prev;
  340.     alloc_block *mblock = (alloc_block *)(cobj - alloc_block_size);
  341.     alloc_state_ptr ap = mblock->cap;
  342.     if ( mblock->save_level == ap->save_level )
  343.      for ( prev = &ap->malloc_chain; *prev != 0; prev = &mblock->next )
  344.        {    mblock = *prev;
  345.         if ( (char *)mblock + alloc_block_size == cobj )
  346.            {    *prev = mblock->next;
  347.             ap->used -= size;
  348.             ap->total -= size;
  349.             (*ap->pfree)((char *)mblock,
  350.                     1, size + alloc_block_size,
  351.                     "large object");
  352.             alloc_print_large('-', '*', cobj, size);
  353.             return;
  354.            }
  355.        }
  356.     alloc_print('-', '?', cobj, size);
  357. }
  358.